package com.zhaopin.theswordreferstooffer;

/**
 * @author yin.peide
 * @date 2021-06-29 17:50
 * 面试题45：圈圈中最后剩下的数字
 * 题目：0,1,…,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字
 * 解法1 ： 我的是这样的
 * 解法2： 创新的解法 //TODO 还未看
 */
public class Offer45 {

    public static void main(String[] args) {
        LinkedNode linkedNode0 = new LinkedNode(0);
        LinkedNode linkedNode1 = new LinkedNode(1);
        LinkedNode linkedNode2 = new LinkedNode(2);
        LinkedNode linkedNode3 = new LinkedNode(3);
        LinkedNode linkedNode4 = new LinkedNode(4);
        linkedNode0.next = linkedNode1;
        linkedNode1.next = linkedNode2;
        linkedNode2.next = linkedNode3;
        linkedNode3.next = linkedNode4;
        linkedNode4.next = linkedNode0;

        //环已经初始化好了
        LinkedNode endLinkNode = getEndNode(linkedNode0);
        System.out.println(endLinkNode.value);


    }


    public static LinkedNode getEndNode(LinkedNode linkedNode) {
        if (linkedNode.value == linkedNode.next.value) {
            return linkedNode;
        }

        //此处可以传递 m ，我的处理方法 m 是2
        LinkedNode toRemove = linkedNode.next.next;
        LinkedNode toRemoveNext = toRemove.next;
        System.out.println("删除了数值：" + toRemove.value);
        linkedNode.next.next = toRemoveNext;
        LinkedNode linkedToNext = linkedNode.next.next;

        return getEndNode(linkedToNext);
    }
}
